A(1) Field of the Invention
The invention generally relates to a television system for the transmission of a digital picture signal from an encoding station to a decoding station via a transmission medium.
More particularly, the invention relates to a television system the encoding station of which is provided with a transform circuit which, for the purpose of realizing a two-dimensional forward discrete cosine transform, is adapted to successively perform two one-dimensional forward discrete cosine transforms for generating basic picture weighting factors, also referred to as coefficients.
The decoding station comprises a transform circuit which, for the purpose of realizing a two-dimensional inverse discrete cosine transform, is adapted to successively perform two one-dimensional inverse discrete cosine transforms in order to recover a picture signal corresponding to the original picture signal from the received basic picture weighting factors.
Such a television system may form part of a television broadcasting system in which case the encoding station forms part of the television broadcasting transmitter and each TV receiver is provided with a decoding station. The transmission medium is the atmosphere in this case and the digital picture signal is transmitted in a given TV channel.
Such a system may alternatively form part of a video recorder in which case the transmission medium is constituted by a video tape. A(2). Description of the Prior Art
As is generally known, a digital picture signal can be subjected to a two-dimensional transform to reduce its bit rate. For performing such a transform, a television picture is partitioned into sub-pictures each of N.times.N pixels and each sub-picture is considered as the sum of N.times.N mutually orthogonal basic pictures B.sub.i,k each likewise of N.times.N pixels and each with its own weighting factor y.sub.i,k ; i, k=0, 1, 2, . . . , N-1.
Due to the correlation between the pixels of a sub-picture, the information is concentrated in a limited number of basis pictures. Only the associated weighting factors are important and the other weighting factors can be ignored. Due to this two-dimensional transform, a block of N.times.N pixels is thus converted into a block of N.times.N weighting factors. Of these weighting factors, however, only a limited number needs to be transferred. For this reason, a significant bit rate reduction is achieved with respect to the direct transmission of the digital picture signal.
In order to determine the weighting factors, a sub-picture of N.times.N pixels is mathematically considered as a N.times.N matrix X and the weighting factors are also arranged in accordance with an N.times.N matrix Y. Furthermore, an orthogonal N.times.N transform matrix A is defined which relates to the selected collection of basic pictures B.sub.i,k. More particularly it holds that: EQU B.sub.i,k =A.sub.i A.sub.k.sup.T ( 1)
In this expression, A.sub.i represents an N.times.N matrix in which each column is equal to the i-th column of the transform matrix A and A.sub.k.sup.T represents a matrix each row of which is equal to the k-th row of the matrix A. These weighting factors now follow from the matrix multiplication EQU Y=A.sup.T XA (2)
In this expression, A.sup.T represents the transposed matrix of A.
For more information relating to the above reference is made to Reference 1.
For the calculation of the weighting factors in accordance with expression (2), both the original transform matrix A and its transposed version should be available. Expression (2) is, however, equivalent to EQU Y.sup.T =(XA).sup.T A (3)
This matrix multiplication only requires the matrix A. More particularly, the product matrix P=XA can be calculated first, subsequently, P can be transposed, and finally Y.sup.T =P.sup.T A can be calculated. A device for performing the matrix multiplication defined in expression (3) is extensively described in Reference 2. For transposing P use is made of an intermediate memory into which P is written row by row and is read column by column. Since X and P.sup.T are multiplied by the same matrix A, the same circuit can in principle be used for both multiplications.
In order to recover the original pixels (matrix X) from the weighting factors thus obtained (matrix Y), these weighting factors are subjected to an inverse transform. This is defined as follows: EQU X=A Y A.sup.T ( 4)
In conformity with the foregoing, this expression is equivalent to EQU X=A (AY.sup.T).sup.T ( 5)
In conformity with the foregoing, the product matrix AY.sup.T will be indicated by P'.
The above-mentioned product matrices P=XA, Y.sup.T =P.sup.T A, P'=AY.sup.T and X=AP'.sup.T are obtained from a series of vector matrix multiplications. For example, in expression (3) a row of X is multiplied by A in order to obtain the corresponding row of P. In this connection such a vector matrix multiplication will be referred to as a one-dimensional transform. More particularly, P is obtained by a one-dimensional forward transform of each of the N rows (vectors) of X and Y.sup.T is obtained by a one-dimensional forward transform of each of the N rows (vectors) of P.sup.T. These transforms are also referred to as one-dimensional because an element of P and Y.sup.T is determined by the elements of only one line of the sub-picture X and P.sup.T, respectively. Since each element of a column of P is determined by another line of the sub-picture X, Y.sup.T is referred to as a two-dimensional transform of X.
Corresponding considerations apply to P' and X in expression (5) in which P' is obtained from one-dimensional inverse transforms of Y.sup.T and in which X is again obtained from one-dimensional inverse transforms of P'.sup.T.
The number of weighting factors which need not be transferred is found to be closely related to the structure of the basis pictures chosen and hence to the transform matrix A chosen. The most optimum and currently frequently used transform matrix is the discrete cosine transform matrix whose elements a.sub.i,k are defined as follows: EQU a.sub.i,k =De.sub.k cos {.pi.(2i+1)k/(2N)} (6)
for i,k =0, 1, 2, . . . N-1 ##EQU1## and with D being a scaling constant which is equal to 2/N if the matrix is used for performing a forward transform and which is equal to 1 if it is used for performing an inverse transform. PA1 r=0, 1, 2, . . . 2.sup.-q N-1 PA1 q=1, 2, 3, . . . Q PA1 u.sub.o,r =d.sub.r (i.e. the r-th pixel or product element of the row); PA1 u.sub.o,N-r =d.sub.N-r (i.e. the (N-r)-th pixel or product element of the row); PA1 Q is the largest integer which is smaller than or equal to -1+.sup.2 logN; PA1 m=0, 1, 2, . . . 2.sup.-q-j N-1 PA1 j=1, 2, . . . .sup.2 log(2.sup.-q N) PA1 w.sub.q,o,m =v.sub.q,m PA1 w.sub.q,o,2 -q.sub.N-1-m =v.sub.q,2 -q.sub.N-1-m
If an N-dimensional vector is multiplied in a conventional manner by an N.times.N matrix, in which case it is referred to as the direct method, N.sup.2 multiplications and N(N-1) additions must be performed for obtaining an N-dimensional product vector.
A discrete cosine transform circuit whose implementation is based on this direct method is described in, for example, Reference 3. So-called fast methods are known from the References 4 and 5 in which the desired result is obtained with considerably fewer multiplications and additions. For example, if N=8, only 13 multiplications and 29 additions are performed by means of the method described in Reference 5. The drawback of this known method is that the word length of the intermediate results must be large in order to obtain sufficiently accurate final results.